The present invention concerns arbitration within a computing system and pertains specifically to an arbiter architecture that allows rapid implementation of arbitration policies.
Within computer systems it is often necessary to allocate limited resources using some sort of arbitration scheme. For example, arbitration is used to allocate access to resources such as memory, networks, interfaces, busses and so on. Arbitration policies determine winners based on system criteria such as requester need, requester priority and system fairness.
Typically, arbiters are individually designed with logic dependent upon the specific arbitration policies implemented. Arbiters are often in a critical timing path. Early estimates of logic complexity help enable complexity verse speed tradeoffs.
When performing arbitration, some bus protocols, for example the I2C bus protocol, use Carrier Sense Multiple Access/Collision Detect (CSMA/CD) for arbitration. See the I2C-Bus Specification, Version 2.0, December 1998 (available from Philips Semiconductor, Inc., or on the internet at xe2x80x9chttp://www-us2. semiconductors.philips.com/acrobat/various/ I2C_BUS_SPECIFICATIONxe2x80x942.pdfxe2x80x9d, pp. 12-13. The Ethernet protocol also uses CSMA/CD. In CSMA/CD arbitration scheme requesters are not synchronized.
The CAN bus protocol uses Carrier Sense Multiple Access/Collision Detect and Arbitration on Message Priority (CSMA/CD+AMP). In this arbitration scheme the identity (ID) numbers are used during arbitration.
In accordance with the preferred embodiment of the present invention, an arbiter allocates resources to a set of requesters. The arbiter includes vector assembly logic and sort logic. The vector assembly logic generates, for each arbitration round, an arbitration vector for each requester in the set of requesters. The sort logic receives the arbitration vectors generated by the vector assembly logic. Based on values of the arbitration vectors, the sort logic designates, for each arbitration round, a requester from the set of requesters as winner.
For example, for each arbitration round, the requester from the set of requesters that is designated as the winner is the requester that has a highest arbitration vector value.
In one embodiment of the present invention a simple round robin arbitration policy is implemented. The vector assembly logic includes a counter that generates a count. A decoder receives the count and generating for each requester a single bit arbitration value as the arbitration vector.
In another embodiment of the present invention, a round robin arbitration policy with a right of refusal is implemented. In this case, a counter generates a count. Assembly logic receives the count and receives a ready bit from each requester in the set of requesters. The assembly logic generates for each requester a multiple bit arbitration value as the arbitration vector.
In another embodiment of the present invention, requester priority arbitration policy with tie-breaking capability is implemented. The vector assembly logic includes a counter that generates a count. The assembly logic receives the count and receives a priority vector from each requester in the set of requesters. The assembly logic uses the priority value and the count to generate a multiple bit arbitration value as the arbitration vector. Alternately, both the counter and a ready bit from each requester may be used for tie-breaking.
The bifurcated architecture of the arbiters set out in various embodiments of the present invention allows for rapid implementation of a variety of arbitration policies.